use rand::{thread_rng, Rng};

// 快速计算 (a*b) % mod
fn q_mul(mut a: u128, mut b: u128, m: u128) -> u128 {
    if b == 0 || a < u128::MAX / b {
        return a * b % m;
    }
    let mut ans = 0;
    while b != 0 {
        if b & 1 == 1 {
            b -= 1;
            ans = (ans + a) % m;
        }
        b >>= 1;
        a = (a + a) % m;
    }
    ans
}
// 快速计算 (a^b) % mod
fn q_pow(a: u128, mut b: u128, m: u128) -> u128 {
    let mut a = a % m;
    let mut res = 1;
    while b > 0 {
        if b & 1 == 1 {
            res = res * a % m;
            // res = q_mul(res, a, m);
        }
        a = a * a % m;
        // a = q_mul(a, a, m);
        b = b >> 1;
    }
    res
}

fn q_pow_2(a: u128, mut b: u128, m: u128) -> u128 {
    let mut a = a % m;
    let mut res = 1;
    while b > 0 {
        if b & 1 == 1 {
            res = q_mul(res, a, m);
        }
        a = q_mul(a, a, m);
        b = b >> 1;
    }
    res
}
fn gcd(a: u128, b: u128) -> u128 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn abs_sub(x: u128, y: u128) -> u128 {
    if x > y {
        x - y
    } else {
        y - x
    }
}
pub fn miller_rabin(n: u128) -> bool {
    if n < 3 || n % 2 == 0 {
        return n == 2;
    }
    if n % 3 == 0 {
        return n == 3;
    }
    let mut u = n - 1;
    let mut t = 0;
    while u % 2 == 0 {
        u = u / 2;
        t = t + 1;
    }
    let test_time = 8;
    for _ in 0..test_time {
        let a = thread_rng().gen_range(2..=n - 2);
        let mut v = q_pow(a, u, n);
        if v == 1 {
            continue;
        }
        let mut s = 0;
        while s < t {
            if v == n - 1 {
                break;
            }
            v = v * v % n;
            s = s + 1;
        }
        if s == t {
            return false;
        }
    }
    true
}

pub fn miller_rabin_2(n: u128) -> bool {
    if n < 3 || n % 2 == 0 {
        return n == 2;
    }
    if n % 3 == 0 {
        return n == 3;
    }
    let mut u = n - 1;
    let mut t = 0;
    while u % 2 == 0 {
        u = u / 2;
        t = t + 1;
    }
    let test_time = 8;
    for _ in 0..test_time {
        let a = thread_rng().gen_range(2..=n - 2);
        let mut v = q_pow_2(a, u, n);
        if v == 1 {
            continue;
        }
        let mut s = 0;
        while s < t {
            if v == n - 1 {
                break;
            }
            v = q_mul(v, v, n);
            s = s + 1;
        }
        if s == t {
            return false;
        }
    }
    true
}

pub fn pollard_rho(x: u128) -> u128 {
    let mut s = 0;
    let mut t = 0;
    let mut rng = thread_rng();
    let c = rng.gen_range(1..x);
    let mut goal = 1;
    let mut val = 1;
    loop {
        for step in 1..=goal {
            t = (q_mul(t, t, x) + c) % x;
            val = q_mul(val, abs_sub(t, s), x);
            if step % 127 == 0 {
                let d = gcd(val, x);
                if d > 1 {
                    return d;
                }
            }
        }
        let d = gcd(val, x);
        if d > 1 {
            return d;
        }
        goal *= 2;
        s = t;
        val = 1;
    }
}
